package MyLinkedList;
class Node{
    //保存节点的值
    public String value;
    //节点的下一个元素
    public Node next;
    public Node(String value){
        this.value = value;
        this.next=null;
    }
}
public class MyLinkedList {
    //把链表的头节点表示出来，此时整个链表就能够获取到了
    //此处不包含傀儡节点，head=null的时候表示空的链表
    private Node head=null;
    //不像顺序表，需要使用size之类的表示“有效元素”区间
    //链表不需要，如果搞一个size记录个数，也是可以的，不记录，通过其他方式获取也行

    //插入元素
    //尾插
    public void addList(String value){
        if (head==null){
            //直接让head指向新的节点即可
            Node newNode=new Node(value);
            head=newNode;
            return;
        }
        //先找到尾巴，把新的节点加到尾巴的后面
        Node tail=head;
        for (;tail!=null;tail=tail.next){
            if (tail.next==null){
                break;
            }
        }
        //通过上述循环，循环结束之后，tail就指向链表的尾巴了
        //创建新的节点
        Node newNode=new Node(value);
        //让尾结点的next指向新的节点
        tail.next=newNode;
        //让新节点的next指向null;
        newNode.next=null;
    }
    //头插
    public void addFirst(String value){
        Node newNode=new Node(value);
        //把新的节点放到头的位置上
        //1.让新节点next指向原来的头节点
        newNode.next = head;
        //2.让头指针指向新的节点
        head=newNode;
    }


    //指定位置插入
    public void add(int index,String value){
        //1.先判断index是否合法
        //index==size的时候，表示尾插，也是合法的情况，不需要抛出异常
        if (index<0||index>size()){
            throw new RuntimeException("下标超出范围");
        }
        if (index==0){
            addFirst(value);
            return;
        }
        //3.根据当前的value值，创建新的节点
        Node newNode=new Node(value);
        //4.找到index要插入的位置的前一个结点
        //插入新节点，需要修改前一个节点的next值
        Node pre=head;
        for (int i=0;i<index-1;i++){
            pre=pre.next;
        }
        //通过上述循环pre就指向index-1的位置
        newNode.next= pre.next;
        pre.next=newNode;
    }
    public int size() {
        int size=0;
        for (Node cur=head;cur!=null;cur=cur.next){
            size++;
        }
        return size;
    }

    //判断某个元素是否在链表中包含
    public boolean contains(String value){
        for (Node cur=head;cur!=null;cur=cur.next){
            //注意，此处的value是String，String的比较应用equals方法
            if (cur.value.equals(value)){
                return true;
            }
        }
        return false;
    }

    public int indexof(String value){
        int index=0;
        for (Node cur=head;cur!=null;cur=cur.next) {
            if (cur.value.equals(value)) {
                return index;
            }
            index++;
        }
        return -1;
    }

    //删除链表中的元素
    //按照下标删除
    public void remove(int index){
        //如果链表为空size就是0了
        if (index<0||index>=size()){
            throw new IndexOutOfBoundsException("下标超出是范围");
        }
        //特殊处理index为0的情况
        if (index==0){
            head=head.next;
            return;
        }
        //2.找到被删除元素的前一个节点的位置
        Node prev=head;
        for (int i=0;i<index-1;i++){
            prev=prev.next;
        }
        //3.循环结束，prev就指向待删除元素的前一个位置
        Node toRemove=prev.next;
        //进行删除操作
        prev.next = toRemove.next;
    }
    //按照值来删除
    public void remove(String value){
        if (head==null) {
            //链表为空直接返回
            return;
        }
        //1.要删除的元素是head
        if (head.value.equals(value)){
            head=head.next;
            return;
        }
        Node prev=head;
        for (;prev!=null; prev = prev.next){
            if (prev.next!=null&&prev.next.value.equals(value)){
                break;
            }
        }
        //通过上述循环，prev就指向代删除元素的前一个位置
        //上述循环结束有两种情况
        //1）value值找到了
        //2）链表遍历完了也没有找到
        if (prev==null){
            return;
        }
        Node toRemove=prev.next;
        prev.next=toRemove.next;
    }

    //清空链表的所有元素
    public void clear(){
        //头指针指向null即可
        head=null;
    }
    @Override
    public String toString() {
        // 通过这个方法, 遍历链表, 构成一个字符串.
        // 遍历的时候, 需要从头结点开始, 进行一个一个元素的打印
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (Node cur=head;cur!=null;cur=cur.next){
            sb.append(cur.value);
            if (cur.next!=null){
                sb.append(",");
            }
        }
        sb.append("]");
        return sb.toString();
    }


    public static void test1(){
        MyLinkedList list=new MyLinkedList();
        list.addList("a");
        list.addList("b");
        list.addList("c");
        System.out.println(list);
    }
    public static void test2(){
        MyLinkedList list=new MyLinkedList();
        list.addFirst("a");
        list.addFirst("b");
        list.addFirst("c");
        System.out.println(list);
    }
    public static void test3(){
        MyLinkedList list = new MyLinkedList();
        list.add(0, "a");
        list.add(1, "b");
        list.add(2, "c");
        list.add(3, "d");
        list.add(0,"e");
        System.out.println(list);
    }
    public static void test4(){
        MyLinkedList list = new MyLinkedList();
        list.add(0, "a");
        list.add(1, "b");
        list.add(2, "c");
        list.add(3, "d");
        System.out.println(list.contains("c"));
        System.out.println(list.contains("e"));
        System.out.println(list.contains("d"));
        System.out.println(list);
    }
    public static void test5() {
        MyLinkedList list = new MyLinkedList();
        list.add(0, "a");
        list.add(1, "b");
        list.add(2, "c");
        list.add(3, "d");
        list.remove(2);
        System.out.println(list);
    }
    public static void test6() {
       MyLinkedList list = new MyLinkedList();
        list.add(0, "a");
        list.add(1, "b");
        list.add(2, "c");
        list.add(3, "d");
        list.remove("a");
        System.out.println(list);
    }
    public static void main(String[] args) {
//        test1();
//        test2();
//        test3();
//        test4();
//        test5();
        test6();
    }
}
